package tulingxueyuan117;

import java.util.ArrayList;

/**
 * Author: Zhang Dongwei
 * Date: 2022/10/27 12:18
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 *
 * 如果有两个中间结点，则返回第二个中间结点。
 */
public class p18_链表的中间节点_876 {
    public static void main(String[] args) {
        ListNode listNode = new  ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(6);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        ListNode res = middleNode(listNode);
        System.out.println(res.val);
    }

//    自己写的，先复制到数组内，然后遍历
    /**
     * 执行用时：
     * 0 ms
     * , 在所有 Java 提交中击败了
     * 100.00%
     * 的用户
     * 内存消耗：
     * 39.3 MB
     * , 在所有 Java 提交中击败了
     * 12.44%
     * 的用户
     * @param head
     * @return
     */
//    public static ListNode middleNode(ListNode head) {
//        ListNode p = head;
//        ArrayList<Integer> list = new ArrayList<>();
//        while (p!=null){
//            list.add(p.val);
//            p = p.next;
//        }
//        int l = list.size();
//        int i = 0;
//        while (i < l/2){
//            head=head.next;
//            i++;
//        }
//        return head;
//    }

    // 在上面的基础上，没有新建数组，直接遍历一次求长度，然后再遍历半长
    /*
    * 执行用时：
0 ms
, 在所有 Java 提交中击败了
100.00%
的用户
内存消耗：
38.9 MB
, 在所有 Java 提交中击败了
69.16%
的用户
    * */
//    public static ListNode middleNode(ListNode head) {
//        ListNode p = head;
//        int l = 0;
//        while (p!=null){
//            l ++ ;
//            p = p.next;
//        }
//        int i = 0;
//        while (i < l/2){
//            head=head.next;
//            i++;
//        }
//        return head;
//    }


//    快慢指针
    /*
    * 执行用时：
0 ms
, 在所有 Java 提交中击败了
100.00%
的用户
内存消耗：
38.9 MB
, 在所有 Java 提交中击败了
70.96%
的用户
    * */
    public static ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

